{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "b1fd7ca5",
   "metadata": {},
   "source": [
    "# 线性表及其逻辑结构"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "82a839df",
   "metadata": {},
   "source": [
    "## 线性表的定义"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "aea8e43a",
   "metadata": {},
   "source": [
    "$~~~~~~~$线性表是具有相同特性的数据元素的一个有限序列。其元素呈线性关系。在线性表中每一元素都有唯一下标与之对应，即第$i$个元素$a_i$的下标为$i-1$。第一个元素称为**表头元素**，最后一个元素称为**表尾元素**。其数据结构用二元组可表示为$L=(D,R)$，其中$D=\\{a_i|1\\le i\\le n,n\\ge0,a_i\\text{为ElemType数据类型}\\}$，$R=\\{r\\}$，$r=\\{<a_i,a_{i+1}>|1\\le i\\le n-1\\}$。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "75d2d148",
   "metadata": {},
   "source": [
    "从其定义可看出线性表具有以下特性：\n",
    "1. **有穷性：**一个线性表中的元素个数是有限的。\n",
    "2. **一致性：**一个线性表中所有元素的性质相同。\n",
    "3. **序列性：**一个线性表中所有元素之间的相对位置都是线性的。并存在唯一的起始元素和终端元素，除此之外，每一个元素仅只有一个**前驱**和一个**后继**。每一个元素在线性表中的位置取决于其序号，因此在线性表中允许存在多个元素值相同的元素。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d23bf844",
   "metadata": {},
   "source": [
    "## 线性表的抽象数据类型描述（ADT）"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "63d2280a",
   "metadata": {},
   "source": [
    "```c\n",
    "ADT 线性表 (List)\n",
    "    \n",
    "Data\n",
    "    线性表的数据对象集合为{a1,a2,a3,…,an},每个元素的类型均为Data Type(int,char,自定义)。其中除了第一个元素a1外，每个元素有且只有一个直接前驱元素；除了最后一个元素an外，每个元素有且只有一个直接后继元素；数据元素之间的关系是一对一的关系。\n",
    "\n",
    "Operation\n",
    "\n",
    "    void InitList(&L);\t// 创造并初始化一个空线性表L。  \n",
    "    void DestoryList(&L);  // 销毁线性表，并释放其占用的空间。\n",
    "    bool ListEmpty(L);  // 判断线性表是否为空，若是，返回true；否则返回false。\n",
    "    int ListLength(L);  // 返回线性表的长度，即当前表中元素的个数。\n",
    "    void DispList(L);  // 遍历输出线性表中的所有元素。\n",
    "    ElemType GetElem(L,i,&e);  // 查找位置i处的元素值，并返回至e。\n",
    "    int LocateElem(L,e);  // 查找指定元素值在表中的位置，若元素不存在，返回0。\n",
    "    bool ListInsert(&L,i,e);  // 在表中指定位置i处插入元素e。若i非法，返回false；否则返回true。\n",
    "    bool ListDelete(&L,i,&e);  // 删除表中第i处元素的值，并用e返回其值。若i非法返回false，否则返回true。\n",
    "    bool ListChange(&L,i,e);  // 修改表中位置i处的元素值为e。若i非法，返回false；否则返回true。\n",
    "    \n",
    "endADT\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4ccdc0a3",
   "metadata": {},
   "source": [
    "## 线性表的顺序存储结构——顺序表"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bf708831",
   "metadata": {},
   "source": [
    "$~~~~~~~$线性表的顺序存储结构是将线性表中的所有元素按照其逻辑顺序依次存储至计算机存储器中指定存储位置开始的一块连续的存储空间中。这种映射称为**直接映射**。线性表的顺序存储结构简称**顺序表**。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1d56b743",
   "metadata": {},
   "source": [
    "### 顺序表基本运算的实现"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "632339d5",
   "metadata": {},
   "source": [
    "定义数组大小："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "1f6b58af",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-05-15T08:37:40.496720Z",
     "start_time": "2021-05-15T08:37:40.49283Z"
    }
   },
   "outputs": [],
   "source": [
    "#define MaxSize 50\n",
    "#include <stdio.h>\n",
    "#include <malloc.h>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c310d0e9",
   "metadata": {},
   "source": [
    "定义元素类型："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "8ad5a96e",
   "metadata": {},
   "outputs": [],
   "source": [
    "typedef int ElemType;"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "807d1217",
   "metadata": {},
   "source": [
    "声明线性表的顺序存储结构：定义一个数组来存储其所有元素，并定义一个整型变量length来存储表中元素的个数。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "7b52a738",
   "metadata": {},
   "outputs": [],
   "source": [
    "typedef struct\n",
    "{\n",
    "    ElemType data[MaxSize];\n",
    "    int length;\n",
    "}SqList;"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1c1e24da",
   "metadata": {},
   "source": [
    "#### 建立顺序表"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "26968fa6",
   "metadata": {},
   "outputs": [],
   "source": [
    "void CreateList(SqList *&L, ElemType a[], int n)\n",
    "{\n",
    "    int i=0,k=0;\n",
    "    L = (SqList *)malloc(sizeof(SqList));\n",
    "    while (i<n)\n",
    "    {\n",
    "        L->data[i] = a[i];\n",
    "        i++,k++;\n",
    "    }\n",
    "    L->length = k;\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f9fb3b8b",
   "metadata": {},
   "source": [
    "#### 初始化线性表"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "39409182",
   "metadata": {},
   "outputs": [],
   "source": [
    "void InitList(SqList *&L)\n",
    "{\n",
    "    L = (SqList *)malloc(sizeof(SqList));\n",
    "    L->length = 0;\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5f5c3152",
   "metadata": {},
   "source": [
    "#### 销毁线性表"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "81ec48da",
   "metadata": {},
   "outputs": [],
   "source": [
    "void DestoryList(SqList *&L)\n",
    "{\n",
    "    free(L);\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "350a7e18",
   "metadata": {},
   "source": [
    "#### 判断线性表是否为空"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "c8989942",
   "metadata": {},
   "outputs": [],
   "source": [
    "bool ListEmpty(SqList *L)\n",
    "{\n",
    "    return L->length==0;\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "be279fef",
   "metadata": {},
   "source": [
    "#### 求线性表的长度"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "fc4ff7b7",
   "metadata": {},
   "outputs": [],
   "source": [
    "int ListLength(SqList *L)\n",
    "{\n",
    "    return L->length;\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "96990f6a",
   "metadata": {},
   "source": [
    "#### 输出线性表"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "0a50a95f",
   "metadata": {},
   "outputs": [],
   "source": [
    "void DispList(SqList *L)\n",
    "{\n",
    "    printf(\"DispList：\");\n",
    "    for(int i=0;i<L->length;i++)\n",
    "    {\n",
    "        printf(\"%d \",L->data[i]);\n",
    "    }\n",
    "    printf(\"\\n\");\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "47acf3ae",
   "metadata": {},
   "source": [
    "#### 求线性表中某位置的元素值"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "86437102",
   "metadata": {},
   "outputs": [],
   "source": [
    "bool GetElem(SqList *L, int i, ElemType &e)\n",
    "{\n",
    "    if(i<0||i>=L->length)\n",
    "        return false;\n",
    "    e = L->data[i];\n",
    "    return true;\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "af9db524",
   "metadata": {},
   "source": [
    "#### 按元素值查找"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "1dcd98d7",
   "metadata": {},
   "outputs": [],
   "source": [
    "int LocateElem(SqList *&L, ElemType e)\n",
    "{\n",
    "    for(int i=0;i<L->length;i++)\n",
    "    {\n",
    "        if(L->data[i] == e)\n",
    "            return i;\n",
    "    }\n",
    "    return -1;\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2c85a2ab",
   "metadata": {},
   "source": [
    "#### 插入数据元素"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "2dacd6bc",
   "metadata": {},
   "outputs": [],
   "source": [
    "bool ListInsert(SqList *&L, int i, ElemType e)\n",
    "{\n",
    "    if(i<0||i>=L->length)\n",
    "        return false;\n",
    "    for(int j=L->length;j>=i;j--)\n",
    "        L->data[j] = L->data[j-1];\n",
    "    L->data[i] = e;\n",
    "    L->length++;\n",
    "    return true;\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4b7f47e7",
   "metadata": {},
   "source": [
    "#### 删除数据元素"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "53143407",
   "metadata": {},
   "outputs": [],
   "source": [
    "bool ElemDelete(SqList *&L, int i, ElemType &e)\n",
    "{\n",
    "    if(i<0||i>=L->length)\n",
    "        return false;\n",
    "    e = L->data[i];\n",
    "    for(int j=i+1;j<L->length;j++)\n",
    "        L->data[j-1] = L->data[j];\n",
    "    L->length--;\n",
    "    return true;\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "15ba71d2",
   "metadata": {},
   "source": [
    "#### 修改数据元素"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "da985abe",
   "metadata": {},
   "outputs": [],
   "source": [
    "bool ElemChange(SqList *&L, int i, ElemType e)\n",
    "{\n",
    "    if(i<0||i>=L->length)\n",
    "        return false;\n",
    "    L->data[i] = e;\n",
    "    return true;    \n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a96f0967",
   "metadata": {},
   "source": [
    "### 测试"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "5d7e1920",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "=========创建线性表=========\n",
      "DispList：1 2 3 4 5 6 7 8 9 \n",
      "=======判断表L是否为空=======\n",
      "false\n",
      "==========求L的长度=========\n",
      "9\n",
      "=======查找位置5处的元素======\n",
      "e: 6\n",
      "=======查找元素8的位置========\n",
      "7\n",
      "=======在位置3插入元素0=======\n",
      "DispList：1 2 3 0 4 5 6 7 8 9 \n",
      "=======删除位置3的元素========\n",
      "e: 0\n",
      "DispList：1 2 3 4 5 6 7 8 9 \n",
      "======修改位置5的元素为10======\n",
      "DispList：1 2 3 4 5 10 7 8 9 \n"
     ]
    }
   ],
   "source": [
    "int a[] = {1,2,3,4,5,6,7,8,9};\n",
    "SqList *L;\n",
    "ElemType e;\n",
    "printf(\"=========创建线性表=========\\n\");\n",
    "CreateList(L,a,9);\n",
    "DispList(L);\n",
    "printf(\"=======判断表L是否为空=======\\n\");\n",
    "if(ListEmpty(L)==true)\n",
    "    printf(\"true\\n\");\n",
    "else\n",
    "    printf(\"false\\n\");\n",
    "printf(\"==========求L的长度=========\\n\");\n",
    "printf(\"%d\\n\",ListLength(L));\n",
    "printf(\"=======查找位置5处的元素======\\n\");\n",
    "GetElem(L,5,e);\n",
    "printf(\"e: %d\\n\",e);\n",
    "printf(\"=======查找元素8的位置========\\n\");\n",
    "printf(\"%d\\n\",LocateElem(L,8));\n",
    "printf(\"=======在位置3插入元素0=======\\n\");\n",
    "ListInsert(L,3,0);\n",
    "DispList(L);\n",
    "printf(\"=======删除位置3的元素========\\n\");\n",
    "ElemDelete(L,3,e);\n",
    "printf(\"e: %d\\n\",e);\n",
    "DispList(L);\n",
    "printf(\"======修改位置5的元素为10======\\n\");\n",
    "ElemChange(L,5,10);\n",
    "DispList(L);\n",
    "DestoryList(L);"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "C++17",
   "language": "C++17",
   "name": "xcpp17"
  },
  "language_info": {
   "codemirror_mode": "text/x-c++src",
   "file_extension": ".cpp",
   "mimetype": "text/x-c++src",
   "name": "c++",
   "version": "17"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {
    "height": "calc(100% - 180px)",
    "left": "10px",
    "top": "150px",
    "width": "279.024px"
   },
   "toc_section_display": true,
   "toc_window_display": true
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
